package main

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func maxProfit(prices []int) int {
	if len(prices) <= 1 {
		return 0
	}
	// dp[i][0] 为第 i 天不持有股票最大盈利 (天数从 0 开始, 与 prices 对齐)
	// dp[i][1] 为第 i 天仍持有股票最大盈利
	dp := make([][2]int, len(prices))
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) // 卖出
		dp[i][1] = max(dp[i-1][1], -prices[i])           // 买入
	}
	return dp[len(prices)-1][0]
}

func main() {
	println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
	println(maxProfit([]int{7, 6, 4, 3, 1}))
}
